package com.umgsai.wx.backend.test.linklist;

import java.util.Random;

public class Main {

    public static void main(String[] args) {
        Node head = new Node(0);

        Node temp = head;
        for (int i = 0; i < 10; i++) {
            Node node = new Node(i + 1);
            temp.setNext(node);
            temp = temp.getNext();
        }

        System.out.println("初始化单链表");

        printLinkList(head);

        System.out.println("反转单链表");

        Node newHead = reverse(head);
        printLinkList(newHead);

        temp = newHead;
        int length = 0;
        while (temp != null) {
            length++;
            temp = temp.getNext();
        }
        System.out.println("单链表长度：" + length);

        // 倒数第N个节点，快慢指针
        int lastIndex = 2;
        Node firstNode = newHead;
        Node secondNode = newHead;
        for (int i = 0; i < lastIndex; i++) {
            if (secondNode == null) {
                throw new RuntimeException("lastIndex超过链表长度");
            }
            secondNode = secondNode.getNext();
        }

        while (secondNode != null) {
            firstNode = firstNode.getNext();
            secondNode = secondNode.getNext();
        }
        System.out.printf("倒数第%d个节点为：%d \n", lastIndex, firstNode.getValue());

        int newDataIndex = 3;
        temp = newHead;
        System.out.println("第" + newDataIndex + "个位置后新增一个节点");
        for (int i = 0; i < newDataIndex - 1; i++) {
            temp = temp.getNext();
        }
        Node newNode = new Node(new Random().nextInt(100));
        newNode.setNext(temp.getNext());
        temp.setNext(newNode);

        printLinkList(newHead);

        // 尾部插入一个节点
        temp = newHead;
        while (true) {
            if (temp.getNext() == null) {
                break;
            }
            temp = temp.getNext();
        }
        System.out.println("尾节点：" + temp.getValue());

        System.out.println("尾结点后增加一个节点");
        Node tail = new Node(118);
        temp.setNext(tail);

        printLinkList(newHead);

        // 删除指定位置的节点，需要考虑删除头节点和尾节点的情况
        int deleteDataIndex = 4;
        temp = newHead;
        for (int i = 0; i < deleteDataIndex - 2; i++) {
            temp = temp.getNext();
        }
        temp.setNext(temp.getNext().getNext());
        System.out.println("删除第" + deleteDataIndex + "个节点");
        printLinkList(newHead);
    }

    public static void printLinkList(Node head) {
        while (head != null) {
            System.out.print(head.getValue() + "  ");
            head = head.getNext();
        }
        System.out.println();
    }

    public static Node reverse(Node head) {
        Node tempHead = head;
        Node prev = null;
        Node next = null;
        while (tempHead != null) {
            next = tempHead.getNext();
            tempHead.setNext(prev);
            prev = tempHead;
            tempHead = next;
        }
        return prev;
    }
}
